package com.peng.leetcode.tree;

/**
 * VerifyPostorder
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 * <p>
 * Created on 2022/12/2
 *
 * @author lupeng
 */
public class VerifyPostorder {

    public static void main(String[] args) {
        int[] a = new int[]{4, 8, 6, 12, 16, 14, 10};
        System.out.println(new VerifyPostorder().verifyPostorder(a));
    }

    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        return recur(postorder, 0, postorder.length - 1);
    }

    boolean recur(int[] postorder, int start, int end) {
        if (start > end) {
            return true;
        }
        int p = end - 2;
        int rootVal = postorder[end];
        while (p > -1 && postorder[p] > rootVal) {
            p--;
        }
        int splitIndex = p;
        while (p > -1 && postorder[p] < rootVal) {
            p--;
        }
        return (start - 1) == p && recur(postorder, start, splitIndex)
                && recur(postorder, splitIndex + 1, end);
    }
}
